home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / h_array.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.3 KB  |  51 lines
  1. {\magonebf 4.5 Hashing arrays (h\_array)}
  2.  
  3. \decltwo h\_array I E 
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $A$ of the parameterized data type \name\ (hashing array)
  8. is an injective mapping from the data type $I$, called the index type of $A$,
  9. to the set of variables of data type $E$, called the element type of $A$. 
  10. $I$ must be an integer, pointer, or item type.
  11.  
  12.  
  13.  
  14. \bigskip
  15. {\bf 2. Creation}
  16.  
  17. \create A (x)
  18.  
  19. creates an injective function $a$ from $I$ to the set of unused variables of 
  20. type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
  21. with $a$.
  22.  
  23.  
  24.  
  25. \bigskip
  26. {\bf 3. Operations}
  27.  
  28. \+\cleartabs & \hskip 1.8truecm & \hskip 5truecm &\cr
  29. \+\opa E\&   {I\ x}  
  30.                       {returns the variable $A(x)$}
  31. \smallskip
  32. \+\op bool defined {I\ x}
  33.                 {returns true if $x \in dom(A)$, false otherwise; here}
  34. \+\nop          {$dom(A)$ is the set of all $x\in I$ for which $A[x]$ has}
  35. \+\nop          {already been executed.}
  36.  
  37. \bigskip
  38. {\bf 4. Iteration}
  39.  
  40. {\bf forall\_defined}($x,A$) 
  41. $\{$ ``the elements from $dom(A)$ are successively assigned to $x$'' $\}$
  42.  
  43.  
  44. \bigskip
  45. {\bf 5. Implementation}
  46.  
  47. Hashing arrays are implemented by dynamic perfect hashing ([DKMMRT88]). 
  48. Access operations $A[x]$ take time $O(1)$. Hashing arrays are more efficient 
  49. than dictionary arrays.
  50.  
  51.